home *** CD-ROM | disk | FTP | other *** search
/ Download Now 8 / Download Now V8.iso / Program / InternetTools / ApacheWebServer1.3.6 / apache_1_3_6_win32.exe / _SETUP.1 / regcomp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-09-15  |  36.9 KB  |  1,549 lines
  1. #include <sys/types.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5. #include <limits.h>
  6. #include <stdlib.h>
  7.  
  8. #include "hsregex.h"
  9. #include "ap_ctype.h"
  10. #include "utils.h"
  11. #include "regex2.h"
  12.  
  13. #include "cclass.h"
  14. #include "cname.h"
  15.  
  16. /*
  17.  * parse structure, passed up and down to avoid global variables and
  18.  * other clumsinesses
  19.  */
  20. struct parse {
  21.     char *next;        /* next character in RE */
  22.     char *end;        /* end of string (-> NUL normally) */
  23.     int error;        /* has an error been seen? */
  24.     sop *strip;        /* malloced strip */
  25.     sopno ssize;        /* malloced strip size (allocated) */
  26.     sopno slen;        /* malloced strip length (used) */
  27.     int ncsalloc;        /* number of csets allocated */
  28.     struct re_guts *g;
  29. #    define    NPAREN    10    /* we need to remember () 1-9 for back refs */
  30.     sopno pbegin[NPAREN];    /* -> ( ([0] unused) */
  31.     sopno pend[NPAREN];    /* -> ) ([0] unused) */
  32. };
  33.  
  34. #include "regcomp.ih"
  35.  
  36. static char nuls[10];        /* place to point scanner in event of error */
  37.  
  38. /*
  39.  * macros for use with parse structure
  40.  * BEWARE:  these know that the parse structure is named `p' !!!
  41.  */
  42. #define    PEEK()    (*p->next)
  43. #define    PEEK2()    (*(p->next+1))
  44. #define    MORE()    (p->next < p->end)
  45. #define    MORE2()    (p->next+1 < p->end)
  46. #define    SEE(c)    (MORE() && PEEK() == (c))
  47. #define    SEETWO(a, b)    (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
  48. #define    EAT(c)    ((SEE(c)) ? (NEXT1(), 1) : 0)
  49. #define    EATTWO(a, b)    ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
  50. #define    NEXT1()    (p->next++)
  51. #define    NEXT2()    (p->next += 2)
  52. #define    NEXTn(n)    (p->next += (n))
  53. #define    GETNEXT()    (*p->next++)
  54. #define    SETERROR(e)    seterr(p, (e))
  55. #define    REQUIRE(co, e)    ((void)((co) || SETERROR(e)))
  56. #define    MUSTSEE(c, e)    (REQUIRE(MORE() && PEEK() == (c), e))
  57. #define    MUSTEAT(c, e)    (REQUIRE(MORE() && GETNEXT() == (c), e))
  58. #define    MUSTNOTSEE(c, e)    (REQUIRE(!MORE() || PEEK() != (c), e))
  59. #define    EMIT(op, sopnd)    doemit(p, (sop)(op), (size_t)(sopnd))
  60. #define    INSERT(op, pos)    doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
  61. #define    AHEAD(pos)        dofwd(p, pos, HERE()-(pos))
  62. #define    ASTERN(sop, pos)    EMIT(sop, HERE()-pos)
  63. #define    HERE()        (p->slen)
  64. #define    THERE()        (p->slen - 1)
  65. #define    THERETHERE()    (p->slen - 2)
  66. #define    DROP(n)    (p->slen -= (n))
  67.  
  68. #ifndef NDEBUG
  69. static int never = 0;        /* for use in asserts; shuts lint up */
  70. #else
  71. #define    never    0        /* some <assert.h>s have bugs too */
  72. #endif
  73.  
  74. /*
  75.  - regcomp - interface for parser and compilation
  76.  = API_EXPORT(int) regcomp(regex_t *, const char *, int);
  77.  = #define    REG_BASIC    0000
  78.  = #define    REG_EXTENDED    0001
  79.  = #define    REG_ICASE    0002
  80.  = #define    REG_NOSUB    0004
  81.  = #define    REG_NEWLINE    0010
  82.  = #define    REG_NOSPEC    0020
  83.  = #define    REG_PEND    0040
  84.  = #define    REG_DUMP    0200
  85.  */
  86. ap_private_extern
  87. API_EXPORT(int)            /* 0 success, otherwise REG_something */
  88. regcomp(preg, pattern, cflags)
  89. regex_t *preg;
  90. const char *pattern;
  91. int cflags;
  92. {
  93.     struct parse pa;
  94.     register struct re_guts *g;
  95.     register struct parse *p = &pa;
  96.     register int i;
  97.     register size_t len;
  98. #ifdef REDEBUG
  99. #    define    GOODFLAGS(f)    (f)
  100. #else
  101. #    define    GOODFLAGS(f)    ((f)&~REG_DUMP)
  102. #endif
  103.  
  104.     cflags = GOODFLAGS(cflags);
  105.     if ((cflags®_EXTENDED) && (cflags®_NOSPEC))
  106.         return(REG_INVARG);
  107.  
  108.     if (cflags®_PEND) {
  109.         if (preg->re_endp < pattern)
  110.             return(REG_INVARG);
  111.         len = preg->re_endp - pattern;
  112.     } else
  113.         len = strlen((char *)pattern);
  114.  
  115.     /* do the mallocs early so failure handling is easy */
  116.     g = (struct re_guts *)malloc(sizeof(struct re_guts) +
  117.                             (NC-1)*sizeof(cat_t));
  118.     if (g == NULL)
  119.         return(REG_ESPACE);
  120.     p->ssize = len/(size_t)2*(size_t)3 + (size_t)1;    /* ugh */
  121.     p->strip = (sop *)malloc(p->ssize * sizeof(sop));
  122.     p->slen = 0;
  123.     if (p->strip == NULL) {
  124.         free((char *)g);
  125.         return(REG_ESPACE);
  126.     }
  127.  
  128.     /* set things up */
  129.     p->g = g;
  130.     p->next = (char *)pattern;    /* convenience; we do not modify it */
  131.     p->end = p->next + len;
  132.     p->error = 0;
  133.     p->ncsalloc = 0;
  134.     for (i = 0; i < NPAREN; i++) {
  135.         p->pbegin[i] = 0;
  136.         p->pend[i] = 0;
  137.     }
  138.     g->csetsize = NC;
  139.     g->sets = NULL;
  140.     g->setbits = NULL;
  141.     g->ncsets = 0;
  142.     g->cflags = cflags;
  143.     g->iflags = 0;
  144.     g->nbol = 0;
  145.     g->neol = 0;
  146.     g->must = NULL;
  147.     g->mlen = 0;
  148.     g->nsub = 0;
  149.     g->ncategories = 1;    /* category 0 is "everything else" */
  150.     g->categories = &g->catspace[-(CHAR_MIN)];
  151.     (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t));
  152.     g->backrefs = 0;
  153.  
  154.     /* do it */
  155.     EMIT(OEND, 0);
  156.     g->firststate = THERE();
  157.     if (cflags®_EXTENDED)
  158.         p_ere(p, OUT);
  159.     else if (cflags®_NOSPEC)
  160.         p_str(p);
  161.     else
  162.         p_bre(p, OUT, OUT);
  163.     EMIT(OEND, 0);
  164.     g->laststate = THERE();
  165.  
  166.     /* tidy up loose ends and fill things in */
  167.     categorize(p, g);
  168.     stripsnug(p, g);
  169.     findmust(p, g);
  170.     g->nplus = pluscount(p, g);
  171.     g->magic = MAGIC2;
  172.     preg->re_nsub = g->nsub;
  173.     preg->re_g = g;
  174.     preg->re_magic = MAGIC1;
  175. #ifndef REDEBUG
  176.     /* not debugging, so can't rely on the assert() in regexec() */
  177.     if (g->iflags&BAD)
  178.         SETERROR(REG_ASSERT);
  179. #endif
  180.  
  181.     /* win or lose, we're done */
  182.     if (p->error != 0)    /* lose */
  183.         regfree(preg);
  184.     return(p->error);
  185. }
  186.  
  187. /*
  188.  - p_ere - ERE parser top level, concatenation and alternation
  189.  == static void p_ere(register struct parse *p, int stop);
  190.  */
  191. static void
  192. p_ere(p, stop)
  193. register struct parse *p;
  194. int stop;            /* character this ERE should end at */
  195. {
  196.     register char c;
  197.     register sopno prevback = 0;
  198.     register sopno prevfwd = 0;
  199.     register sopno conc;
  200.     register int first = 1;        /* is this the first alternative? */
  201.  
  202.     for (;;) {
  203.         /* do a bunch of concatenated expressions */
  204.         conc = HERE();
  205.         while (MORE() && (c = PEEK()) != '|' && c != stop)
  206.             p_ere_exp(p);
  207.         REQUIRE(HERE() != conc, REG_EMPTY);    /* require nonempty */
  208.  
  209.         if (!EAT('|'))
  210.             break;        /* NOTE BREAK OUT */
  211.  
  212.         if (first) {
  213.             INSERT(OCH_, conc);    /* offset is wrong */
  214.             prevfwd = conc;
  215.             prevback = conc;
  216.             first = 0;
  217.         }
  218.         ASTERN(OOR1, prevback);
  219.         prevback = THERE();
  220.         AHEAD(prevfwd);            /* fix previous offset */
  221.         prevfwd = HERE();
  222.         EMIT(OOR2, 0);            /* offset is very wrong */
  223.     }
  224.  
  225.     if (!first) {        /* tail-end fixups */
  226.         AHEAD(prevfwd);
  227.         ASTERN(O_CH, prevback);
  228.     }
  229.  
  230.     assert(!MORE() || SEE(stop));
  231. }
  232.  
  233. /*
  234.  - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
  235.  == static void p_ere_exp(register struct parse *p);
  236.  */
  237. static void
  238. p_ere_exp(p)
  239. register struct parse *p;
  240. {
  241.     register char c;
  242.     register sopno pos;
  243.     register int count;
  244.     register int count2;
  245.     register sopno subno;
  246.     int wascaret = 0;
  247.  
  248.     assert(MORE());        /* caller should have ensured this */
  249.     c = GETNEXT();
  250.  
  251.     pos = HERE();
  252.     switch (c) {
  253.     case '(':
  254.         REQUIRE(MORE(), REG_EPAREN);
  255.         p->g->nsub++;
  256.         subno = p->g->nsub;
  257.         if (subno < NPAREN)
  258.             p->pbegin[subno] = HERE();
  259.         EMIT(OLPAREN, subno);
  260.         if (!SEE(')'))
  261.             p_ere(p, ')');
  262.         if (subno < NPAREN) {
  263.             p->pend[subno] = HERE();
  264.             assert(p->pend[subno] != 0);
  265.         }
  266.         EMIT(ORPAREN, subno);
  267.         MUSTEAT(')', REG_EPAREN);
  268.         break;
  269. #ifndef POSIX_MISTAKE
  270.     case ')':        /* happens only if no current unmatched ( */
  271.         /*
  272.          * You may ask, why the ifndef?  Because I didn't notice
  273.          * this until slightly too late for 1003.2, and none of the
  274.          * other 1003.2 regular-expression reviewers noticed it at
  275.          * all.  So an unmatched ) is legal POSIX, at least until
  276.          * we can get it fixed.
  277.          */
  278.         SETERROR(REG_EPAREN);
  279.         break;
  280. #endif
  281.     case '^':
  282.         EMIT(OBOL, 0);
  283.         p->g->iflags |= USEBOL;
  284.         p->g->nbol++;
  285.         wascaret = 1;
  286.         break;
  287.     case '$':
  288.         EMIT(OEOL, 0);
  289.         p->g->iflags |= USEEOL;
  290.         p->g->neol++;
  291.         break;
  292.     case '|':
  293.         SETERROR(REG_EMPTY);
  294.         break;
  295.     case '*':
  296.     case '+':
  297.     case '?':
  298.         SETERROR(REG_BADRPT);
  299.         break;
  300.     case '.':
  301.         if (p->g->cflags®_NEWLINE)
  302.             nonnewline(p);
  303.         else
  304.             EMIT(OANY, 0);
  305.         break;
  306.     case '[':
  307.         p_bracket(p);
  308.         break;
  309.     case '\\':
  310.         REQUIRE(MORE(), REG_EESCAPE);
  311.         c = GETNEXT();
  312.         ordinary(p, c);
  313.         break;
  314.     case '{':        /* okay as ordinary except if digit follows */
  315.         REQUIRE(!MORE() || !ap_isdigit(PEEK()), REG_BADRPT);
  316.         /* FALLTHROUGH */
  317.     default:
  318.         ordinary(p, c);
  319.         break;
  320.     }
  321.  
  322.     if (!MORE())
  323.         return;
  324.     c = PEEK();
  325.     /* we call { a repetition if followed by a digit */
  326.     if (!( c == '*' || c == '+' || c == '?' ||
  327.                 (c == '{' && MORE2() && ap_isdigit(PEEK2())) ))
  328.         return;        /* no repetition, we're done */
  329.     NEXT1();
  330.  
  331.     REQUIRE(!wascaret, REG_BADRPT);
  332.     switch (c) {
  333.     case '*':    /* implemented as +? */
  334.         /* this case does not require the (y|) trick, noKLUDGE */
  335.         INSERT(OPLUS_, pos);
  336.         ASTERN(O_PLUS, pos);
  337.         INSERT(OQUEST_, pos);
  338.         ASTERN(O_QUEST, pos);
  339.         break;
  340.     case '+':
  341.         INSERT(OPLUS_, pos);
  342.         ASTERN(O_PLUS, pos);
  343.         break;
  344.     case '?':
  345.         /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  346.         INSERT(OCH_, pos);        /* offset slightly wrong */
  347.         ASTERN(OOR1, pos);        /* this one's right */
  348.         AHEAD(pos);            /* fix the OCH_ */
  349.         EMIT(OOR2, 0);            /* offset very wrong... */
  350.         AHEAD(THERE());            /* ...so fix it */
  351.         ASTERN(O_CH, THERETHERE());
  352.         break;
  353.     case '{':
  354.         count = p_count(p);
  355.         if (EAT(',')) {
  356.             if (ap_isdigit(PEEK())) {
  357.                 count2 = p_count(p);
  358.                 REQUIRE(count <= count2, REG_BADBR);
  359.             } else        /* single number with comma */
  360.                 count2 = INFINITY;
  361.         } else        /* just a single number */
  362.             count2 = count;
  363.         repeat(p, pos, count, count2);
  364.         if (!EAT('}')) {    /* error heuristics */
  365.             while (MORE() && PEEK() != '}')
  366.                 NEXT1();
  367.             REQUIRE(MORE(), REG_EBRACE);
  368.             SETERROR(REG_BADBR);
  369.         }
  370.         break;
  371.     }
  372.  
  373.     if (!MORE())
  374.         return;
  375.     c = PEEK();
  376.     if (!( c == '*' || c == '+' || c == '?' ||
  377.                 (c == '{' && MORE2() && ap_isdigit(PEEK2())) ) )
  378.         return;
  379.     SETERROR(REG_BADRPT);
  380. }
  381.  
  382. /*
  383.  - p_str - string (no metacharacters) "parser"
  384.  == static void p_str(register struct parse *p);
  385.  */
  386. static void
  387. p_str(p)
  388. register struct parse *p;
  389. {
  390.     REQUIRE(MORE(), REG_EMPTY);
  391.     while (MORE())
  392.         ordinary(p, GETNEXT());
  393. }
  394.  
  395. /*
  396.  - p_bre - BRE parser top level, anchoring and concatenation
  397.  == static void p_bre(register struct parse *p, register int end1, \
  398.  ==    register int end2);
  399.  * Giving end1 as OUT essentially eliminates the end1/end2 check.
  400.  *
  401.  * This implementation is a bit of a kludge, in that a trailing $ is first
  402.  * taken as an ordinary character and then revised to be an anchor.  The
  403.  * only undesirable side effect is that '$' gets included as a character
  404.  * category in such cases.  This is fairly harmless; not worth fixing.
  405.  * The amount of lookahead needed to avoid this kludge is excessive.
  406.  */
  407. static void
  408. p_bre(p, end1, end2)
  409. register struct parse *p;
  410. register int end1;        /* first terminating character */
  411. register int end2;        /* second terminating character */
  412. {
  413.     register sopno start = HERE();
  414.     register int first = 1;            /* first subexpression? */
  415.     register int wasdollar = 0;
  416.  
  417.     if (EAT('^')) {
  418.         EMIT(OBOL, 0);
  419.         p->g->iflags |= USEBOL;
  420.         p->g->nbol++;
  421.     }
  422.     while (MORE() && !SEETWO(end1, end2)) {
  423.         wasdollar = p_simp_re(p, first);
  424.         first = 0;
  425.     }
  426.     if (wasdollar) {    /* oops, that was a trailing anchor */
  427.         DROP(1);
  428.         EMIT(OEOL, 0);
  429.         p->g->iflags |= USEEOL;
  430.         p->g->neol++;
  431.     }
  432.  
  433.     REQUIRE(HERE() != start, REG_EMPTY);    /* require nonempty */
  434. }
  435.  
  436. /*
  437.  - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
  438.  == static int p_simp_re(register struct parse *p, int starordinary);
  439.  */
  440. static int            /* was the simple RE an unbackslashed $? */
  441. p_simp_re(p, starordinary)
  442. register struct parse *p;
  443. int starordinary;        /* is a leading * an ordinary character? */
  444. {
  445.     register int c;
  446.     register int count;
  447.     register int count2;
  448.     register sopno pos;
  449.     register int i;
  450.     register sopno subno;
  451. #    define    BACKSL    (1<<CHAR_BIT)
  452.  
  453.     pos = HERE();        /* repetion op, if any, covers from here */
  454.  
  455.     assert(MORE());        /* caller should have ensured this */
  456.     c = GETNEXT();
  457.     if (c == '\\') {
  458.         REQUIRE(MORE(), REG_EESCAPE);
  459.         c = BACKSL | (unsigned char)GETNEXT();
  460.     }
  461.     switch (c) {
  462.     case '.':
  463.         if (p->g->cflags®_NEWLINE)
  464.             nonnewline(p);
  465.         else
  466.             EMIT(OANY, 0);
  467.         break;
  468.     case '[':
  469.         p_bracket(p);
  470.         break;
  471.     case BACKSL|'{':
  472.         SETERROR(REG_BADRPT);
  473.         break;
  474.     case BACKSL|'(':
  475.         p->g->nsub++;
  476.         subno = p->g->nsub;
  477.         if (subno < NPAREN)
  478.             p->pbegin[subno] = HERE();
  479.         EMIT(OLPAREN, subno);
  480.         /* the MORE here is an error heuristic */
  481.         if (MORE() && !SEETWO('\\', ')'))
  482.             p_bre(p, '\\', ')');
  483.         if (subno < NPAREN) {
  484.             p->pend[subno] = HERE();
  485.             assert(p->pend[subno] != 0);
  486.         }
  487.         EMIT(ORPAREN, subno);
  488.         REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
  489.         break;
  490.     case BACKSL|')':    /* should not get here -- must be user */
  491.     case BACKSL|'}':
  492.         SETERROR(REG_EPAREN);
  493.         break;
  494.     case BACKSL|'1':
  495.     case BACKSL|'2':
  496.     case BACKSL|'3':
  497.     case BACKSL|'4':
  498.     case BACKSL|'5':
  499.     case BACKSL|'6':
  500.     case BACKSL|'7':
  501.     case BACKSL|'8':
  502.     case BACKSL|'9':
  503.         i = (c&~BACKSL) - '0';
  504.         assert(i < NPAREN);
  505.         if (p->pend[i] != 0) {
  506.             assert(i <= p->g->nsub);
  507.             EMIT(OBACK_, i);
  508.             assert(p->pbegin[i] != 0);
  509.             assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
  510.             assert(OP(p->strip[p->pend[i]]) == ORPAREN);
  511.             (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
  512.             EMIT(O_BACK, i);
  513.         } else
  514.             SETERROR(REG_ESUBREG);
  515.         p->g->backrefs = 1;
  516.         break;
  517.     case '*':
  518.         REQUIRE(starordinary, REG_BADRPT);
  519.         /* FALLTHROUGH */
  520.     default:
  521.         ordinary(p, c &~ BACKSL);
  522.         break;
  523.     }
  524.  
  525.     if (EAT('*')) {        /* implemented as +? */
  526.         /* this case does not require the (y|) trick, noKLUDGE */
  527.         INSERT(OPLUS_, pos);
  528.         ASTERN(O_PLUS, pos);
  529.         INSERT(OQUEST_, pos);
  530.         ASTERN(O_QUEST, pos);
  531.     } else if (EATTWO('\\', '{')) {
  532.         count = p_count(p);
  533.         if (EAT(',')) {
  534.             if (MORE() && ap_isdigit(PEEK())) {
  535.                 count2 = p_count(p);
  536.                 REQUIRE(count <= count2, REG_BADBR);
  537.             } else        /* single number with comma */
  538.                 count2 = INFINITY;
  539.         } else        /* just a single number */
  540.             count2 = count;
  541.         repeat(p, pos, count, count2);
  542.         if (!EATTWO('\\', '}')) {    /* error heuristics */
  543.             while (MORE() && !SEETWO('\\', '}'))
  544.                 NEXT1();
  545.             REQUIRE(MORE(), REG_EBRACE);
  546.             SETERROR(REG_BADBR);
  547.         }
  548.     } else if (c == (unsigned char)'$')    /* $ (but not \$) ends it */
  549.         return(1);
  550.  
  551.     return(0);
  552. }
  553.  
  554. /*
  555.  - p_count - parse a repetition count
  556.  == static int p_count(register struct parse *p);
  557.  */
  558. static int            /* the value */
  559. p_count(p)
  560. register struct parse *p;
  561. {
  562.     register int count = 0;
  563.     register int ndigits = 0;
  564.  
  565.     while (MORE() && ap_isdigit(PEEK()) && count <= DUPMAX) {
  566.         count = count*10 + (GETNEXT() - '0');
  567.         ndigits++;
  568.     }
  569.  
  570.     REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
  571.     return(count);
  572. }
  573.  
  574. /*
  575.  - p_bracket - parse a bracketed character list
  576.  == static void p_bracket(register struct parse *p);
  577.  *
  578.  * Note a significant property of this code:  if the allocset() did SETERROR,
  579.  * no set operations are done.
  580.  */
  581. static void
  582. p_bracket(p)
  583. register struct parse *p;
  584. {
  585.     register cset *cs = allocset(p);
  586.     register int invert = 0;
  587.  
  588.     /* Dept of Truly Sickening Special-Case Kludges */
  589.     if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
  590.         EMIT(OBOW, 0);
  591.         NEXTn(6);
  592.         return;
  593.     }
  594.     if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
  595.         EMIT(OEOW, 0);
  596.         NEXTn(6);
  597.         return;
  598.     }
  599.  
  600.     if (EAT('^'))
  601.         invert++;    /* make note to invert set at end */
  602.     if (EAT(']'))
  603.         CHadd(cs, ']');
  604.     else if (EAT('-'))
  605.         CHadd(cs, '-');
  606.     while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
  607.         p_b_term(p, cs);
  608.     if (EAT('-'))
  609.         CHadd(cs, '-');
  610.     MUSTEAT(']', REG_EBRACK);
  611.  
  612.     if (p->error != 0)    /* don't mess things up further */
  613.         return;
  614.  
  615.     if (p->g->cflags®_ICASE) {
  616.         register int i;
  617.         register int ci;
  618.  
  619.         for (i = p->g->csetsize - 1; i >= 0; i--)
  620.             if (CHIN(cs, i) && ap_isalpha(i)) {
  621.                 ci = othercase(i);
  622.                 if (ci != i)
  623.                     CHadd(cs, ci);
  624.             }
  625.         if (cs->multis != NULL)
  626.             mccase(p, cs);
  627.     }
  628.     if (invert) {
  629.         register int i;
  630.  
  631.         for (i = p->g->csetsize - 1; i >= 0; i--)
  632.             if (CHIN(cs, i))
  633.                 CHsub(cs, i);
  634.             else
  635.                 CHadd(cs, i);
  636.         if (p->g->cflags®_NEWLINE)
  637.             CHsub(cs, '\n');
  638.         if (cs->multis != NULL)
  639.             mcinvert(p, cs);
  640.     }
  641.  
  642.     assert(cs->multis == NULL);        /* xxx */
  643.  
  644.     if (nch(p, cs) == 1) {        /* optimize singleton sets */
  645.         ordinary(p, firstch(p, cs));
  646.         freeset(p, cs);
  647.     } else
  648.         EMIT(OANYOF, freezeset(p, cs));
  649. }
  650.  
  651. /*
  652.  - p_b_term - parse one term of a bracketed character list
  653.  == static void p_b_term(register struct parse *p, register cset *cs);
  654.  */
  655. static void
  656. p_b_term(p, cs)
  657. register struct parse *p;
  658. register cset *cs;
  659. {
  660.     register char c;
  661.     register char start, finish;
  662.     register int i;
  663.  
  664.     /* classify what we've got */
  665.     switch ((MORE()) ? PEEK() : '\0') {
  666.     case '[':
  667.         c = (MORE2()) ? PEEK2() : '\0';
  668.         break;
  669.     case '-':
  670.         SETERROR(REG_ERANGE);
  671.         return;            /* NOTE RETURN */
  672.         break;
  673.     default:
  674.         c = '\0';
  675.         break;
  676.     }
  677.  
  678.     switch (c) {
  679.     case ':':        /* character class */
  680.         NEXT2();
  681.         REQUIRE(MORE(), REG_EBRACK);
  682.         c = PEEK();
  683.         REQUIRE(c != '-' && c != ']', REG_ECTYPE);
  684.         p_b_cclass(p, cs);
  685.         REQUIRE(MORE(), REG_EBRACK);
  686.         REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
  687.         break;
  688.     case '=':        /* equivalence class */
  689.         NEXT2();
  690.         REQUIRE(MORE(), REG_EBRACK);
  691.         c = PEEK();
  692.         REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
  693.         p_b_eclass(p, cs);
  694.         REQUIRE(MORE(), REG_EBRACK);
  695.         REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
  696.         break;
  697.     default:        /* symbol, ordinary character, or range */
  698. /* xxx revision needed for multichar stuff */
  699.         start = p_b_symbol(p);
  700.         if (SEE('-') && MORE2() && PEEK2() != ']') {
  701.             /* range */
  702.             NEXT1();
  703.             if (EAT('-'))
  704.                 finish = '-';
  705.             else
  706.                 finish = p_b_symbol(p);
  707.         } else
  708.             finish = start;
  709. /* xxx what about signed chars here... */
  710.         REQUIRE(start <= finish, REG_ERANGE);
  711.         for (i = start; i <= finish; i++)
  712.             CHadd(cs, i);
  713.         break;
  714.     }
  715. }
  716.  
  717. /*
  718.  - p_b_cclass - parse a character-class name and deal with it
  719.  == static void p_b_cclass(register struct parse *p, register cset *cs);
  720.  */
  721. static void
  722. p_b_cclass(p, cs)
  723. register struct parse *p;
  724. register cset *cs;
  725. {
  726.     register char *sp = p->next;
  727.     register struct cclass *cp;
  728.     register size_t len;
  729.     register char *u;
  730.     register char c;
  731.  
  732.     while (MORE() && ap_isalpha(PEEK()))
  733.         NEXT1();
  734.     len = p->next - sp;
  735.     for (cp = cclasses; cp->name != NULL; cp++)
  736.         if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
  737.             break;
  738.     if (cp->name == NULL) {
  739.         /* oops, didn't find it */
  740.         SETERROR(REG_ECTYPE);
  741.         return;
  742.     }
  743.  
  744.     u = cp->chars;
  745.     while ((c = *u++) != '\0')
  746.         CHadd(cs, c);
  747.     for (u = cp->multis; *u != '\0'; u += strlen(u) + 1)
  748.         MCadd(p, cs, u);
  749. }
  750.  
  751. /*
  752.  - p_b_eclass - parse an equivalence-class name and deal with it
  753.  == static void p_b_eclass(register struct parse *p, register cset *cs);
  754.  *
  755.  * This implementation is incomplete. xxx
  756.  */
  757. static void
  758. p_b_eclass(p, cs)
  759. register struct parse *p;
  760. register cset *cs;
  761. {
  762.     register char c;
  763.  
  764.     c = p_b_coll_elem(p, '=');
  765.     CHadd(cs, c);
  766. }
  767.  
  768. /*
  769.  - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
  770.  == static char p_b_symbol(register struct parse *p);
  771.  */
  772. static char            /* value of symbol */
  773. p_b_symbol(p)
  774. register struct parse *p;
  775. {
  776.     register char value;
  777.  
  778.     REQUIRE(MORE(), REG_EBRACK);
  779.     if (!EATTWO('[', '.'))
  780.         return(GETNEXT());
  781.  
  782.     /* collating symbol */
  783.     value = p_b_coll_elem(p, '.');
  784.     REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
  785.     return(value);
  786. }
  787.  
  788. /*
  789.  - p_b_coll_elem - parse a collating-element name and look it up
  790.  == static char p_b_coll_elem(register struct parse *p, int endc);
  791.  */
  792. static char            /* value of collating element */
  793. p_b_coll_elem(p, endc)
  794. register struct parse *p;
  795. int endc;            /* name ended by endc,']' */
  796. {
  797.     register char *sp = p->next;
  798.     register struct cname *cp;
  799.     register int len;
  800.  
  801.     while (MORE() && !SEETWO(endc, ']'))
  802.         NEXT1();
  803.     if (!MORE()) {
  804.         SETERROR(REG_EBRACK);
  805.         return(0);
  806.     }
  807.     len = p->next - sp;
  808.     for (cp = cnames; cp->name != NULL; cp++)
  809.         if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
  810.             return(cp->code);    /* known name */
  811.     if (len == 1)
  812.         return(*sp);    /* single character */
  813.     SETERROR(REG_ECOLLATE);            /* neither */
  814.     return(0);
  815. }
  816.  
  817. /*
  818.  - othercase - return the case counterpart of an alphabetic
  819.  == static char othercase(int ch);
  820.  */
  821. static char            /* if no counterpart, return ch */
  822. othercase(ch)
  823. int ch;
  824. {
  825.     assert(ap_isalpha(ch));
  826.     if (ap_isupper(ch))
  827.         return(ap_tolower(ch));
  828.     else if (ap_islower(ch))
  829.         return(ap_toupper(ch));
  830.     else            /* peculiar, but could happen */
  831.         return(ch);
  832. }
  833.  
  834. /*
  835.  - bothcases - emit a dualcase version of a two-case character
  836.  == static void bothcases(register struct parse *p, int ch);
  837.  *
  838.  * Boy, is this implementation ever a kludge...
  839.  */
  840. static void
  841. bothcases(p, ch)
  842. register struct parse *p;
  843. int ch;
  844. {
  845.     register char *oldnext = p->next;
  846.     register char *oldend = p->end;
  847.     char bracket[3];
  848.  
  849.     assert(othercase(ch) != ch);    /* p_bracket() would recurse */
  850.     p->next = bracket;
  851.     p->end = bracket+2;
  852.     bracket[0] = ch;
  853.     bracket[1] = ']';
  854.     bracket[2] = '\0';
  855.     p_bracket(p);
  856.     assert(p->next == bracket+2);
  857.     p->next = oldnext;
  858.     p->end = oldend;
  859. }
  860.  
  861. /*
  862.  - ordinary - emit an ordinary character
  863.  == static void ordinary(register struct parse *p, register int ch);
  864.  */
  865. static void
  866. ordinary(p, ch)
  867. register struct parse *p;
  868. register int ch;
  869. {
  870.     register cat_t *cap = p->g->categories;
  871.  
  872.     if ((p->g->cflags®_ICASE) && ap_isalpha(ch) && othercase(ch) != ch)
  873.         bothcases(p, ch);
  874.     else {
  875.         EMIT(OCHAR, (unsigned char)ch);
  876.         if (cap[ch] == 0)
  877.             cap[ch] = p->g->ncategories++;
  878.     }
  879. }
  880.  
  881. /*
  882.  - nonnewline - emit REG_NEWLINE version of OANY
  883.  == static void nonnewline(register struct parse *p);
  884.  *
  885.  * Boy, is this implementation ever a kludge...
  886.  */
  887. static void
  888. nonnewline(p)
  889. register struct parse *p;
  890. {
  891.     register char *oldnext = p->next;
  892.     register char *oldend = p->end;
  893.     char bracket[4];
  894.  
  895.     p->next = bracket;
  896.     p->end = bracket+3;
  897.     bracket[0] = '^';
  898.     bracket[1] = '\n';
  899.     bracket[2] = ']';
  900.     bracket[3] = '\0';
  901.     p_bracket(p);
  902.     assert(p->next == bracket+3);
  903.     p->next = oldnext;
  904.     p->end = oldend;
  905. }
  906.  
  907. /*
  908.  - repeat - generate code for a bounded repetition, recursively if needed
  909.  == static void repeat(register struct parse *p, sopno start, int from, int to);
  910.  */
  911. static void
  912. repeat(p, start, from, to)
  913. register struct parse *p;
  914. sopno start;            /* operand from here to end of strip */
  915. int from;            /* repeated from this number */
  916. int to;                /* to this number of times (maybe INFINITY) */
  917. {
  918.     register sopno finish = HERE();
  919. #    define    N    2
  920. #    define    INF    3
  921. #    define    REP(f, t)    ((f)*8 + (t))
  922. #    define    MAP(n)    (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
  923.     register sopno copy;
  924.  
  925.     if (p->error != 0)    /* head off possible runaway recursion */
  926.         return;
  927.  
  928.     assert(from <= to);
  929.  
  930.     switch (REP(MAP(from), MAP(to))) {
  931.     case REP(0, 0):            /* must be user doing this */
  932.         DROP(finish-start);    /* drop the operand */
  933.         break;
  934.     case REP(0, 1):            /* as x{1,1}? */
  935.     case REP(0, N):            /* as x{1,n}? */
  936.     case REP(0, INF):        /* as x{1,}? */
  937.         /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  938.         INSERT(OCH_, start);        /* offset is wrong... */
  939.         repeat(p, start+1, 1, to);
  940.         ASTERN(OOR1, start);
  941.         AHEAD(start);            /* ... fix it */
  942.         EMIT(OOR2, 0);
  943.         AHEAD(THERE());
  944.         ASTERN(O_CH, THERETHERE());
  945.         break;
  946.     case REP(1, 1):            /* trivial case */
  947.         /* done */
  948.         break;
  949.     case REP(1, N):            /* as x?x{1,n-1} */
  950.         /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  951.         INSERT(OCH_, start);
  952.         ASTERN(OOR1, start);
  953.         AHEAD(start);
  954.         EMIT(OOR2, 0);            /* offset very wrong... */
  955.         AHEAD(THERE());            /* ...so fix it */
  956.         ASTERN(O_CH, THERETHERE());
  957.         copy = dupl(p, start+1, finish+1);
  958.         assert(copy == finish+4);
  959.         repeat(p, copy, 1, to-1);
  960.         break;
  961.     case REP(1, INF):        /* as x+ */
  962.         INSERT(OPLUS_, start);
  963.         ASTERN(O_PLUS, start);
  964.         break;
  965.     case REP(N, N):            /* as xx{m-1,n-1} */
  966.         copy = dupl(p, start, finish);
  967.         repeat(p, copy, from-1, to-1);
  968.         break;
  969.     case REP(N, INF):        /* as xx{n-1,INF} */
  970.         copy = dupl(p, start, finish);
  971.         repeat(p, copy, from-1, to);
  972.         break;
  973.     default:            /* "can't happen" */
  974.         SETERROR(REG_ASSERT);    /* just in case */
  975.         break;
  976.     }
  977. }
  978.  
  979. /*
  980.  - seterr - set an error condition
  981.  == static int seterr(register struct parse *p, int e);
  982.  */
  983. static int            /* useless but makes type checking happy */
  984. seterr(p, e)
  985. register struct parse *p;
  986. int e;
  987. {
  988.     if (p->error == 0)    /* keep earliest error condition */
  989.         p->error = e;
  990.     p->next = nuls;        /* try to bring things to a halt */
  991.     p->end = nuls;
  992.     return(0);        /* make the return value well-defined */
  993. }
  994.  
  995. /*
  996.  - allocset - allocate a set of characters for []
  997.  == static cset *allocset(register struct parse *p);
  998.  */
  999. static cset *
  1000. allocset(p)
  1001. register struct parse *p;
  1002. {
  1003.     register int no = p->g->ncsets++;
  1004.     register size_t nc;
  1005.     register size_t nbytes;
  1006.     register cset *cs;
  1007.     register size_t css = (size_t)p->g->csetsize;
  1008.     register int i;
  1009.  
  1010.     if (no >= p->ncsalloc) {    /* need another column of space */
  1011.         p->ncsalloc += CHAR_BIT;
  1012.         nc = p->ncsalloc;
  1013.         assert(nc % CHAR_BIT == 0);
  1014.         nbytes = nc / CHAR_BIT * css;
  1015.         if (p->g->sets == NULL)
  1016.             p->g->sets = (cset *)malloc(nc * sizeof(cset));
  1017.         else
  1018.             p->g->sets = (cset *)realloc((char *)p->g->sets,
  1019.                             nc * sizeof(cset));
  1020.         if (p->g->setbits == NULL)
  1021.             p->g->setbits = (uch *)malloc(nbytes);
  1022.         else {
  1023.             p->g->setbits = (uch *)realloc((char *)p->g->setbits,
  1024.                                 nbytes);
  1025.             /* xxx this isn't right if setbits is now NULL */
  1026.             for (i = 0; i < no; i++)
  1027.                 p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
  1028.         }
  1029.         if (p->g->sets != NULL && p->g->setbits != NULL)
  1030.             (void) memset((char *)p->g->setbits + (nbytes - css),
  1031.                                 0, css);
  1032.         else {
  1033.             no = 0;
  1034.             SETERROR(REG_ESPACE);
  1035.             /* caller's responsibility not to do set ops */
  1036.         }
  1037.     }
  1038.  
  1039.     assert(p->g->sets != NULL);    /* xxx */
  1040.     cs = &p->g->sets[no];
  1041.     cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
  1042.     cs->mask = 1 << ((no) % CHAR_BIT);
  1043.     cs->hash = 0;
  1044.     cs->smultis = 0;
  1045.     cs->multis = NULL;
  1046.  
  1047.     return(cs);
  1048. }
  1049.  
  1050. /*
  1051.  - freeset - free a now-unused set
  1052.  == static void freeset(register struct parse *p, register cset *cs);
  1053.  */
  1054. static void
  1055. freeset(p, cs)
  1056. register struct parse *p;
  1057. register cset *cs;
  1058. {
  1059.     register int i;
  1060.     register cset *top = &p->g->sets[p->g->ncsets];
  1061.     register size_t css = (size_t)p->g->csetsize;
  1062.  
  1063.     for (i = 0; i < css; i++)
  1064.         CHsub(cs, i);
  1065.     if (cs == top-1)    /* recover only the easy case */
  1066.         p->g->ncsets--;
  1067. }
  1068.  
  1069. /*
  1070.  - freezeset - final processing on a set of characters
  1071.  == static int freezeset(register struct parse *p, register cset *cs);
  1072.  *
  1073.  * The main task here is merging identical sets.  This is usually a waste
  1074.  * of time (although the hash code minimizes the overhead), but can win
  1075.  * big if REG_ICASE is being used.  REG_ICASE, by the way, is why the hash
  1076.  * is done using addition rather than xor -- all ASCII [aA] sets xor to
  1077.  * the same value!
  1078.  */
  1079. static int            /* set number */
  1080. freezeset(p, cs)
  1081. register struct parse *p;
  1082. register cset *cs;
  1083. {
  1084.     register uch h = cs->hash;
  1085.     register int i;
  1086.     register cset *top = &p->g->sets[p->g->ncsets];
  1087.     register cset *cs2;
  1088.     register size_t css = (size_t)p->g->csetsize;
  1089.  
  1090.     /* look for an earlier one which is the same */
  1091.     for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
  1092.         if (cs2->hash == h && cs2 != cs) {
  1093.             /* maybe */
  1094.             for (i = 0; i < css; i++)
  1095.                 if (!!CHIN(cs2, i) != !!CHIN(cs, i))
  1096.                     break;        /* no */
  1097.             if (i == css)
  1098.                 break;            /* yes */
  1099.         }
  1100.  
  1101.     if (cs2 < top) {    /* found one */
  1102.         freeset(p, cs);
  1103.         cs = cs2;
  1104.     }
  1105.  
  1106.     return((int)(cs - p->g->sets));
  1107. }
  1108.  
  1109. /*
  1110.  - firstch - return first character in a set (which must have at least one)
  1111.  == static int firstch(register struct parse *p, register cset *cs);
  1112.  */
  1113. static int            /* character; there is no "none" value */
  1114. firstch(p, cs)
  1115. register struct parse *p;
  1116. register cset *cs;
  1117. {
  1118.     register int i;
  1119.     register size_t css = (size_t)p->g->csetsize;
  1120.  
  1121.     for (i = 0; i < css; i++)
  1122.         if (CHIN(cs, i))
  1123.             return((char)i);
  1124.     assert(never);
  1125.     return(0);        /* arbitrary */
  1126. }
  1127.  
  1128. /*
  1129.  - nch - number of characters in a set
  1130.  == static int nch(register struct parse *p, register cset *cs);
  1131.  */
  1132. static int
  1133. nch(p, cs)
  1134. register struct parse *p;
  1135. register cset *cs;
  1136. {
  1137.     register int i;
  1138.     register size_t css = (size_t)p->g->csetsize;
  1139.     register int n = 0;
  1140.  
  1141.     for (i = 0; i < css; i++)
  1142.         if (CHIN(cs, i))
  1143.             n++;
  1144.     return(n);
  1145. }
  1146.  
  1147. /*
  1148.  - mcadd - add a collating element to a cset
  1149.  == static void mcadd(register struct parse *p, register cset *cs, \
  1150.  ==    register char *cp);
  1151.  */
  1152. static void
  1153. mcadd(p, cs, cp)
  1154. register struct parse *p;
  1155. register cset *cs;
  1156. register char *cp;
  1157. {
  1158.     register size_t oldend = cs->smultis;
  1159.  
  1160.     cs->smultis += strlen(cp) + 1;
  1161.     if (cs->multis == NULL)
  1162.         cs->multis = malloc(cs->smultis);
  1163.     else
  1164.         cs->multis = realloc(cs->multis, cs->smultis);
  1165.     if (cs->multis == NULL) {
  1166.         SETERROR(REG_ESPACE);
  1167.         return;
  1168.     }
  1169.  
  1170.     (void) strcpy(cs->multis + oldend - 1, cp);
  1171.     cs->multis[cs->smultis - 1] = '\0';
  1172. }
  1173.  
  1174.  
  1175. /*
  1176.  - mcinvert - invert the list of collating elements in a cset
  1177.  == static void mcinvert(register struct parse *p, register cset *cs);
  1178.  *
  1179.  * This would have to know the set of possibilities.  Implementation
  1180.  * is deferred.
  1181.  */
  1182. static void
  1183. mcinvert(p, cs)
  1184. register struct parse *p;
  1185. register cset *cs;
  1186. {
  1187.     assert(cs->multis == NULL);    /* xxx */
  1188. }
  1189.  
  1190. /*
  1191.  - mccase - add case counterparts of the list of collating elements in a cset
  1192.  == static void mccase(register struct parse *p, register cset *cs);
  1193.  *
  1194.  * This would have to know the set of possibilities.  Implementation
  1195.  * is deferred.
  1196.  */
  1197. static void
  1198. mccase(p, cs)
  1199. register struct parse *p;
  1200. register cset *cs;
  1201. {
  1202.     assert(cs->multis == NULL);    /* xxx */
  1203. }
  1204.  
  1205. /*
  1206.  - isinsets - is this character in any sets?
  1207.  == static int isinsets(register struct re_guts *g, int c);
  1208.  */
  1209. static int            /* predicate */
  1210. isinsets(g, c)
  1211. register struct re_guts *g;
  1212. int c;
  1213. {
  1214.     register uch *col;
  1215.     register int i;
  1216.     register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
  1217.     register unsigned uc = (unsigned char)c;
  1218.  
  1219.     for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
  1220.         if (col[uc] != 0)
  1221.             return(1);
  1222.     return(0);
  1223. }
  1224.  
  1225. /*
  1226.  - samesets - are these two characters in exactly the same sets?
  1227.  == static int samesets(register struct re_guts *g, int c1, int c2);
  1228.  */
  1229. static int            /* predicate */
  1230. samesets(g, c1, c2)
  1231. register struct re_guts *g;
  1232. int c1;
  1233. int c2;
  1234. {
  1235.     register uch *col;
  1236.     register int i;
  1237.     register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
  1238.     register unsigned uc1 = (unsigned char)c1;
  1239.     register unsigned uc2 = (unsigned char)c2;
  1240.  
  1241.     for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
  1242.         if (col[uc1] != col[uc2])
  1243.             return(0);
  1244.     return(1);
  1245. }
  1246.  
  1247. /*
  1248.  - categorize - sort out character categories
  1249.  == static void categorize(struct parse *p, register struct re_guts *g);
  1250.  */
  1251. static void
  1252. categorize(p, g)
  1253. struct parse *p;
  1254. register struct re_guts *g;
  1255. {
  1256.     register cat_t *cats = g->categories;
  1257.     register int c;
  1258.     register int c2;
  1259.     register cat_t cat;
  1260.  
  1261.     /* avoid making error situations worse */
  1262.     if (p->error != 0)
  1263.         return;
  1264.  
  1265.     for (c = CHAR_MIN; c <= CHAR_MAX; c++)
  1266.         if (cats[c] == 0 && isinsets(g, c)) {
  1267.             cat = g->ncategories++;
  1268.             cats[c] = cat;
  1269.             for (c2 = c+1; c2 <= CHAR_MAX; c2++)
  1270.                 if (cats[c2] == 0 && samesets(g, c, c2))
  1271.                     cats[c2] = cat;
  1272.         }
  1273. }
  1274.  
  1275. /*
  1276.  - dupl - emit a duplicate of a bunch of sops
  1277.  == static sopno dupl(register struct parse *p, sopno start, sopno finish);
  1278.  */
  1279. static sopno            /* start of duplicate */
  1280. dupl(p, start, finish)
  1281. register struct parse *p;
  1282. sopno start;            /* from here */
  1283. sopno finish;            /* to this less one */
  1284. {
  1285.     register sopno ret = HERE();
  1286.     register sopno len = finish - start;
  1287.  
  1288.     assert(finish >= start);
  1289.     if (len == 0)
  1290.         return(ret);
  1291.     enlarge(p, p->ssize + len);    /* this many unexpected additions */
  1292.     assert(p->ssize >= p->slen + len);
  1293.     (void) memcpy((char *)(p->strip + p->slen),
  1294.         (char *)(p->strip + start), (size_t)len*sizeof(sop));
  1295.     p->slen += len;
  1296.     return(ret);
  1297. }
  1298.  
  1299. /*
  1300.  - doemit - emit a strip operator
  1301.  == static void doemit(register struct parse *p, sop op, size_t opnd);
  1302.  *
  1303.  * It might seem better to implement this as a macro with a function as
  1304.  * hard-case backup, but it's just too big and messy unless there are
  1305.  * some changes to the data structures.  Maybe later.
  1306.  */
  1307. static void
  1308. doemit(p, op, opnd)
  1309. register struct parse *p;
  1310. sop op;
  1311. size_t opnd;
  1312. {
  1313.     /* avoid making error situations worse */
  1314.     if (p->error != 0)
  1315.         return;
  1316.  
  1317.     /* deal with oversize operands ("can't happen", more or less) */
  1318.     assert(opnd < 1<<OPSHIFT);
  1319.  
  1320.     /* deal with undersized strip */
  1321.     if (p->slen >= p->ssize)
  1322.         enlarge(p, (p->ssize+1) / 2 * 3);    /* +50% */
  1323.     assert(p->slen < p->ssize);
  1324.  
  1325.     /* finally, it's all reduced to the easy case */
  1326.     p->strip[p->slen++] = SOP(op, opnd);
  1327. }
  1328.  
  1329. /*
  1330.  - doinsert - insert a sop into the strip
  1331.  == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos);
  1332.  */
  1333. static void
  1334. doinsert(p, op, opnd, pos)
  1335. register struct parse *p;
  1336. sop op;
  1337. size_t opnd;
  1338. sopno pos;
  1339. {
  1340.     register sopno sn;
  1341.     register sop s;
  1342.     register int i;
  1343.  
  1344.     /* avoid making error situations worse */
  1345.     if (p->error != 0)
  1346.         return;
  1347.  
  1348.     sn = HERE();
  1349.     EMIT(op, opnd);        /* do checks, ensure space */
  1350.     assert(HERE() == sn+1);
  1351.     s = p->strip[sn];
  1352.  
  1353.     /* adjust paren pointers */
  1354.     assert(pos > 0);
  1355.     for (i = 1; i < NPAREN; i++) {
  1356.         if (p->pbegin[i] >= pos) {
  1357.             p->pbegin[i]++;
  1358.         }
  1359.         if (p->pend[i] >= pos) {
  1360.             p->pend[i]++;
  1361.         }
  1362.     }
  1363.  
  1364.     memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
  1365.                         (HERE()-pos-1)*sizeof(sop));
  1366.     p->strip[pos] = s;
  1367. }
  1368.  
  1369. /*
  1370.  - dofwd - complete a forward reference
  1371.  == static void dofwd(register struct parse *p, sopno pos, sop value);
  1372.  */
  1373. static void
  1374. dofwd(p, pos, value)
  1375. register struct parse *p;
  1376. register sopno pos;
  1377. sop value;
  1378. {
  1379.     /* avoid making error situations worse */
  1380.     if (p->error != 0)
  1381.         return;
  1382.  
  1383.     assert(value < 1<<OPSHIFT);
  1384.     p->strip[pos] = OP(p->strip[pos]) | value;
  1385. }
  1386.  
  1387. /*
  1388.  - enlarge - enlarge the strip
  1389.  == static void enlarge(register struct parse *p, sopno size);
  1390.  */
  1391. static void
  1392. enlarge(p, size)
  1393. register struct parse *p;
  1394. register sopno size;
  1395. {
  1396.     register sop *sp;
  1397.  
  1398.     if (p->ssize >= size)
  1399.         return;
  1400.  
  1401.     sp = (sop *)realloc(p->strip, size*sizeof(sop));
  1402.     if (sp == NULL) {
  1403.         SETERROR(REG_ESPACE);
  1404.         return;
  1405.     }
  1406.     p->strip = sp;
  1407.     p->ssize = size;
  1408. }
  1409.  
  1410. /*
  1411.  - stripsnug - compact the strip
  1412.  == static void stripsnug(register struct parse *p, register struct re_guts *g);
  1413.  */
  1414. static void
  1415. stripsnug(p, g)
  1416. register struct parse *p;
  1417. register struct re_guts *g;
  1418. {
  1419.     g->nstates = p->slen;
  1420.     g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop));
  1421.     if (g->strip == NULL) {
  1422.         SETERROR(REG_ESPACE);
  1423.         g->strip = p->strip;
  1424.     }
  1425. }
  1426.  
  1427. /*
  1428.  - findmust - fill in must and mlen with longest mandatory literal string
  1429.  == static void findmust(register struct parse *p, register struct re_guts *g);
  1430.  *
  1431.  * This algorithm could do fancy things like analyzing the operands of |
  1432.  * for common subsequences.  Someday.  This code is simple and finds most
  1433.  * of the interesting cases.
  1434.  *
  1435.  * Note that must and mlen got initialized during setup.
  1436.  */
  1437. static void
  1438. findmust(p, g)
  1439. struct parse *p;
  1440. register struct re_guts *g;
  1441. {
  1442.     register sop *scan;
  1443.     sop *start = NULL;
  1444.     register sop *newstart = NULL;
  1445.     register sopno newlen;
  1446.     register sop s;
  1447.     register char *cp;
  1448.     register sopno i;
  1449.  
  1450.     /* avoid making error situations worse */
  1451.     if (p->error != 0)
  1452.         return;
  1453.  
  1454.     /* find the longest OCHAR sequence in strip */
  1455.     newlen = 0;
  1456.     scan = g->strip + 1;
  1457.     do {
  1458.         s = *scan++;
  1459.         switch (OP(s)) {
  1460.         case OCHAR:        /* sequence member */
  1461.             if (newlen == 0)        /* new sequence */
  1462.                 newstart = scan - 1;
  1463.             newlen++;
  1464.             break;
  1465.         case OPLUS_:        /* things that don't break one */
  1466.         case OLPAREN:
  1467.         case ORPAREN:
  1468.             break;
  1469.         case OQUEST_:        /* things that must be skipped */
  1470.         case OCH_:
  1471.             scan--;
  1472.             do {
  1473.                 scan += OPND(s);
  1474.                 s = *scan;
  1475.                 /* assert() interferes w debug printouts */
  1476.                 if (OP(s) != O_QUEST && OP(s) != O_CH &&
  1477.                             OP(s) != OOR2) {
  1478.                     g->iflags |= BAD;
  1479.                     return;
  1480.                 }
  1481.             } while (OP(s) != O_QUEST && OP(s) != O_CH);
  1482.             /* fallthrough */
  1483.         default:        /* things that break a sequence */
  1484.             if (newlen > g->mlen) {        /* ends one */
  1485.                 start = newstart;
  1486.                 g->mlen = newlen;
  1487.             }
  1488.             newlen = 0;
  1489.             break;
  1490.         }
  1491.     } while (OP(s) != OEND);
  1492.  
  1493.     if (g->mlen == 0)        /* there isn't one */
  1494.         return;
  1495.  
  1496.     /* turn it into a character string */
  1497.     g->must = malloc((size_t)g->mlen + 1);
  1498.     if (g->must == NULL) {        /* argh; just forget it */
  1499.         g->mlen = 0;
  1500.         return;
  1501.     }
  1502.     cp = g->must;
  1503.     scan = start;
  1504.     for (i = g->mlen; i > 0; i--) {
  1505.         while (OP(s = *scan++) != OCHAR)
  1506.             continue;
  1507.         assert(cp < g->must + g->mlen);
  1508.         *cp++ = (char)OPND(s);
  1509.     }
  1510.     assert(cp == g->must + g->mlen);
  1511.     *cp++ = '\0';        /* just on general principles */
  1512. }
  1513.  
  1514. /*
  1515.  - pluscount - count + nesting
  1516.  == static sopno pluscount(register struct parse *p, register struct re_guts *g);
  1517.  */
  1518. static sopno            /* nesting depth */
  1519. pluscount(p, g)
  1520. struct parse *p;
  1521. register struct re_guts *g;
  1522. {
  1523.     register sop *scan;
  1524.     register sop s;
  1525.     register sopno plusnest = 0;
  1526.     register sopno maxnest = 0;
  1527.  
  1528.     if (p->error != 0)
  1529.         return(0);    /* there may not be an OEND */
  1530.  
  1531.     scan = g->strip + 1;
  1532.     do {
  1533.         s = *scan++;
  1534.         switch (OP(s)) {
  1535.         case OPLUS_:
  1536.             plusnest++;
  1537.             break;
  1538.         case O_PLUS:
  1539.             if (plusnest > maxnest)
  1540.                 maxnest = plusnest;
  1541.             plusnest--;
  1542.             break;
  1543.         }
  1544.     } while (OP(s) != OEND);
  1545.     if (plusnest != 0)
  1546.         g->iflags |= BAD;
  1547.     return(maxnest);
  1548. }
  1549.